package com.lwl.Algorithmic_data_structure.class20暴力递归2动态规划;

/**
 * @author lwl
 * @Description 给你一个9*10的二维棋盘,现在让你从 (0,0) 移动到 (x,y),且只能必须要刚好走k步,共有多少种走法
 * 🐎只能走日字
 * @date 2023/6/11 11:20
 */
public class Code02HouseJump {

    public static void main(String[] args) {
        System.out.println(houseJump(new int[9][10], 7, 7, 10));
        System.out.println(houseJump2(new int[9][10], 7, 7, 10));
    }

    static private int houseJump2(int[][] board, int x, int y, int k) {
        // k步到0步,所以需要k+1
        int[][][] dp = new int[board.length][board[0].length][k + 1];
        // 因为rest步数是一直依赖rest-1的,所以知道rest-1这一层二维数组,就能完全推出rest这一层
        dp[y][x][0] = 1;// 看递归中base case
        for (int rest = 1; rest <= k; rest++) {
            for (int curX = 0; curX < board[0].length; curX++) {
                for (int curY = 0; curY < board.length; curY++) {
                    dp[curY][curX][rest] = pick(dp, curX + 2, curY + 1, rest - 1)
                            + pick(dp, curX + 1, curY + 2, rest - 1)
                            + pick(dp, curX - 1, curY + 2, rest - 1)
                            + pick(dp, curX - 2, curY + 1, rest - 1)
                            + pick(dp, curX - 2, curY - 1, rest - 1)
                            + pick(dp, curX - 1, curY - 2, rest - 1)
                            + pick(dp, curX + 1, curY - 2, rest - 1)
                            + pick(dp, curX + 2, curY - 1, rest - 1);
                }
            }
        }
        return dp[0][0][k];
    }

    static private int pick(int[][][] dp, int x, int y, int rest) {
        if (x < 0 || x >= dp[0].length || y < 0 || y >= dp.length) {
            return 0;
        }
        return dp[y][x][rest];
    }

    static private int houseJump(int[][] board, int x, int y, int rest) {
        return process(board, x, 0, y, 0, rest);
    }

    private static int process(int[][] board, int x, int curX, int y, int curY, int rest) {
        // 越界了,直接返回0 ; 这个最好在判断步数前判断,仅仅是逻辑上更好看,这两个判断根本不可能冲突
        if (curX < 0 || curX >= board[0].length || curY < 0 || curY >= board.length) {
            return 0;
        }
        if (rest == 0) {
            if (x == curX && y == curY) {
                return 1;
            }
            return 0;
        }

        // 分别测试上下左右走,是否越界在下一次递归中判断
        int p1 = process(board, x, curX + 2, y, curY + 1, rest - 1);
        int p2 = process(board, x, curX + 1, y, curY + 2, rest - 1);
        int p3 = process(board, x, curX - 1, y, curY + 2, rest - 1);
        int p4 = process(board, x, curX - 2, y, curY + 1, rest - 1);
        int p5 = process(board, x, curX - 2, y, curY - 1, rest - 1);
        int p6 = process(board, x, curX - 1, y, curY - 2, rest - 1);
        int p7 = process(board, x, curX + 1, y, curY - 2, rest - 1);
        int p8 = process(board, x, curX + 2, y, curY - 1, rest - 1);

        return p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8;
    }


}
